/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._938;

/**
 * 给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。
 * <p>
 * 二叉搜索树保证具有唯一的值。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：root = [10,5,15,3,7,null,18], L = 7, R = 15
 * 输出：32
 * 示例 2：
 * <p>
 * 输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
 * 输出：23
 *  
 * <p>
 * 提示：
 * <p>
 * 树中的结点数量最多为 10000 个。
 * 最终的答案保证小于 2^31。
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._938
 * @ClassName: RangeSumOfBst
 * @Author: linyaonan
 * @Date: 2020/1/7 10:56
 */
public class RangeSumOfBst {
    Integer sum = 0;

    public int rangeSumBST(TreeNode root, int L, int R) {
        sum = 0;
        bfs(root, L, R);
        return sum;
    }

    private void bfs(TreeNode node, int l, int r) {
        if (node != null) {
            int t = node.val;
            if (t < l) {
                bfs(node.right, l, r);
            } else if (t > r) {
                bfs(node.left, l, r);
            } else {
                bfs(node.left, l, r);
                sum += t;
                bfs(node.right, l, r);
            }
        }
    }
}
